package com.lagou.subjecttwo;

import java.util.Scanner;

/**
 * 最长子串
 */
public class SubjectTwoMain {
    public static void main(String[] args) {
        System.out.println("输入两个字符串：");
        //String s1 = "asdafghjka";
        //String s2 = "aaasdfg";
        Scanner sc = new Scanner(System.in);
        String s1 = sc.next();
        String s2 = sc.next();
        String maxString = "";
        if (s1.length() > s2.length())
            maxString = MarchMax(s1, s2, 0, s2.length());
        else
            maxString = MarchMax(s2, s1, 0, s1.length());
        //输出
        System.out.println("最长子串为：" + maxString);
    }

    /**
     * 匹配最长子串
     *
     * @param big   长子串
     * @param small 短子串
     * @param i     起始位置
     * @param j     结束位置
     * @return
     */
    public static String MarchMax(String big, String small, int i, int j) {
        //如果开始位置，结束位置，一样，说明没有匹配得了，直接返回
        if (i == j)
            return "";
        //截取对应匹配的大小的字符串
        String marchString = small.substring(i, j);
        boolean have = big.contains(marchString);
        //匹配结果
        if (have)
            //如果匹配到了，直接返回匹配到的字符串
            return marchString;
        else {
            //没有匹配到，有两种情况
            //一种左边往右移一位
            String x = MarchMax(big, small, i + 1, j);
            //一种右边往左一一位
            String y = MarchMax(big, small, i, j - 1);
            //判断最终返回值长度，取最长的
            if (x.length() > y.length())
                return x;
            else
                return y;
        }
    }
}
